class Node(object):
    def __init__(self, data=None):
        self.data = data
        self.next = None
        self.prev = None


class FIFO(object):
    def __init__(self, max_length):
        # new一个队头
        self.head = Node()
        # new一个队尾
        self.tail = Node()
        # 队列的最大宽度
        self.max_length = max_length
        self.length = 0

        self.head.next = self.tail
        self.tail.prev = self.head

    # 判断队列是否队满
    def is_full(self):
        return self.length == self.max_length

    # 判断队列是否队空
    def is_empty(self):
        return self.length == 0

    def unShift(self, data):
        assert not self.is_full()

        newNode = Node()
        newNode.data = data

        # 队尾的前一个节点
        prevNode = self.tail.prev
        # 前一个节点与添加节点的位置关系
        prevNode.next = newNode
        newNode.prev = prevNode

        # 队尾与添加节点的位置关系
        self.tail.prev = newNode
        newNode.next = self.tail

        self.length += 1

    def Shift(self):
        assert not self.is_empty()

        # 要删除的节点
        delNode = self.head.next
        # 删除节点的下一节点
        newNode = delNode.next

        self.head.next = newNode
        newNode.prev = self.head

        self.length -= 1
        return delNode.data

    def __iter__(self):
        newNode = self.head.next

        while newNode != self.tail:
            yield newNode.data
            newNode = newNode.next


if __name__ == '__main__':
    l = FIFO(11)
    for i in range(0, 10):
        l.unShift(i)
    l.unShift(12)

    # for i in l:
    #     print(i)

    l.Shift()
    l.Shift()
    for i in l:
        print(i)



